#include<stdio.h>

int fun(int n,int m){
	if(m==1)return 1;
	if(n==0)return 1;
	if(n<0)return 0;
	return fun(n,m-1)+fun(n-m,m);
}
int main(){
	
	int n,m,a,i,sum=0;
	scanf("%d",&a);
	for(i=0;i<a;i++){
		scanf("%d%d",&n,&m);
		sum=0;
		sum=sum+fun(n,m);	
		printf("%d\n",sum);
	}
	return 0;
}